#include "EFDR.h"
#include"global.h"
#include<unordered_map>
#include<string>
#include"function.h"
#include<iostream>
#include<cmath>
using namespace std;
EFDR::EFDR(void)
{
}


EFDR::~EFDR(void)
{
}

unordered_map<int,string> EFDR::_Dic;


void EFDR::_Fill_X(string& pp)
{
	uint32_t ppl=pp.length();
	uint32_t j,k;
	//left xxxx1->11111,xxxx0->00000.
	if(pp[0]=='X')
	{
		for(k=0;k<pp.length()&&pp[k]=='X';k++){}
		for(j=0;j<k;j++)
		{
			if(pp[j]!='X')
				throw msg("not X");
			pp[j]=pp[k];
		}
	}
	//right 0xx->001,00x->001.1一锟斤拷.
	if(pp[ppl-1]=='X')
	{
		for(k=ppl-1;k>0&&pp[k]=='X';k--){}
		for(j=k+1;j<ppl-1;j++)pp[j]=pp[k];
		pp[ppl-1]=char(pp[k]^0x1);
	}
	if(pp[ppl-2]=='X')
		for(j=ppl-2;pp[j]=='X';j--)pp[j]=pp[ppl-1]^0x1;

	//middle 0xxx0,1xxxx1.
	for(j=1;j<ppl-1;j++)
		if(pp[j]=='X')
		{
			char x0=pp[j-1];
			for(k=j;k<ppl&&pp[k]=='X';k++){}
			if(x0==pp[k])
			{
				for(;j<k;j++)
				{
					if(pp[j]!='X')
						throw msg("not X");
					pp[j]=x0;
				}
				j--;
			}
			else
			{
				for(;j<k;j++)
				{
					if(pp[j]!='X')
						throw msg("not X");
					pp[j]='0';
				}
				j--;
			}
		}
}


//Dynamic fill
#define N 2000 //vectors
#define M 300  //length
int s[N*M];//锟斤拷锟斤拷纬锟�
int m[N*M],m_posix[N*M];//锟斤拷锟斤拷锟斤拷
int code_num;//锟轿筹拷锟斤拷
inline void code_set(const string &v,int len)//锟斤拷始锟斤拷s,m,code_num
{
	int i,j,k=1;
	//11111xxxx0000xxxx11
	//11111xxxx0000xxxx10
	//last
	int last;
	if(v[len-1]==v[len-2])
	{
		for(last=len-1;v[last]==v[len-1]&&last>0;last--){}
	}
	else
	{
		for(last=len-2;v[last]==v[len-2]&&last>0;last--){}
	}

	for(i=0;i<=last;)
	{
		for(j=i;v[j]==v[i];j++){}
		s[k]=j-i-1;
		if(i==0)s[k]++;//first
		int u;
		for(u=j;v[u]=='X';u++){}
		m[k]=u-j;
		m_posix[k]=j;
		k++;
		i=u;
	}
	if(v[len-1]==v[len-2])s[k]=len-2-last;
	else s[k]=len-3-last;
	m[k]=0;
	m_posix[k]=0;
	code_num=k;
}
int efdr_lenth(int length)//锟斤拷锟斤拷双锟轿程憋拷锟诫长锟斤拷
{
	if(length==0)
		return 0;
	int x=int(1+2*int(ceil((log(length+2.0)/log(2.0)-1))));
	return x;
}
//dynamic program
int y[N*M/10][N],p[N*M/10][N];int a[N*M];
int marginAssignAlgorithm(string &v,int len)
{
	int i,j,k;


	for(i=0;i<=m[1];i++)
		y[1][i]=efdr_lenth(s[1]+i);
	for(i=2;i<=code_num;i++)
		for(j=0;j<=m[i];j++)
		{
			int miny=y[i-1][0]+efdr_lenth(s[i]+j+m[i-1]);//k=0
			int mink=0;
			for(k=1;k<=m[i-1];k++)
			{
				int t=y[i-1][k]+efdr_lenth(s[i]+j+m[i-1]-k);
				if(miny>t)
				{
					miny=t;
					mink=k;
				}
			}
			y[i][j]=miny;
			p[i][j]=mink;
		}
		a[code_num]=0;
		for(i=code_num;i>=2;i--)
		{
			a[i-1]=p[i][a[i]];
		}
		//fill
		for(i=1;i<code_num;i++)
			if(m[i]>0)
			{
				for(j=0;j<a[i];j++)
				{
					if(v[m_posix[i]+j]!='X')printf("error:%d %d %d %d\n",m_posix[i],s[i],m[i],a[i]);//
					v[m_posix[i]+j]=v[m_posix[i]-1];
				}

				for(;v[m_posix[i]+j]=='X';j++)v[m_posix[i]+j]=v[m_posix[i]-1]^1;
			}
			return y[code_num][0];
}

char pp[N*M];
void EFDR::_Fill_X_Dynamic(string& pp)
{
	/*Casa@130414c
	1 预锟斤拷锟斤拷
	锟斤拷1锟斤拷锟斤拷锟斤拷锟�xxx0,1xxxx1.
	锟斤拷2锟斤拷锟斤拷呓锟絰xxx1->11111,xxxx0->00000.
	锟斤拷3锟斤拷锟揭边斤拷0xx->001,00x->001.1一锟斤拷.
	2 锟斤拷态锟芥划
	锟斤拷准锟斤拷 0x1x000xxx111xxx0x1

	*/
	//1 预锟斤拷锟斤拷
	uint32_t j,k,ppl=pp.length();
	//锟斤拷1锟斤拷锟斤拷呓锟絰xxx1->11111,xxxx0->00000.
	if(pp[0]=='X')
	{
		for(k=0;k<pp.length()&&pp[k]=='X';k++){}
		for(j=0;j<k;j++)
		{
			if(pp[j]!='X')printf("error:%d\n",__LINE__);
			pp[j]=pp[k];
		}
	}
	//锟斤拷2锟斤拷锟揭边斤拷0xx->001,00x->001.1一锟斤拷.
	if(pp[ppl-1]=='X')
	{
		for(k=ppl-1;k>0&&pp[k]=='X';k--){}
		for(j=k+1;j<ppl-1;j++)pp[j]=pp[k];
		pp[ppl-1]=pp[k]^0x1;
	}
	if(pp[ppl-2]=='X')
		for(j=ppl-2;pp[j]=='X';j--)pp[j]=pp[ppl-1]^0x1;
	//锟斤拷3锟斤拷锟斤拷锟斤拷锟�xxx0,1xxxx1.
	for(j=1;j<ppl-1;j++)
		if(pp[j]=='X')
		{
			char x0=pp[j-1];
			for(k=j;k<ppl&&pp[k]=='X';k++){}
			if(x0==pp[k])
			{
				for(;j<k;j++)
				{
					if(pp[j]!='X')printf("error:%d\n",__LINE__);
					pp[j]=x0;
				}
				j--;
			}
			else j=k-1;
			//cout<<j<<endl;
		}
		//2 锟斤拷态锟芥划
		//锟斤拷准锟斤拷 0x1x000xxx111xxx0x1
		code_set(pp,ppl);
		marginAssignAlgorithm(pp,ppl);
}


string EFDR::_Run(int size)
{
	if(_Dic.find(size)!=_Dic.end())
		return _Dic.at(size);
	int group=int(ceil((log(size+2.0)/log(2.0)-1)));
	string _runcode;
	for(int i=1;i<group;i++)
		_runcode+='1';
	_runcode+='0';

	int tail=size-(1<<group)+1;
	for(int i=group-1;i>=0;i--)
		_runcode+=((tail>>i)&1)+'0';
	_Dic.insert(make_pair(size,_runcode));
	return _runcode;
}

unique_ptr<string> EFDR::_Code(const string& _data)
{
	string data=_data;
	unique_ptr<string> _efdr(new string);
	for(uint32_t i=0;i<data.length();i++)
	{
		int l=0;
		char _c=data.at(i);
		while(i<data.length()&&data.at(i)==_c)
		{
			i++;
			l++;
		}
		*_efdr+=_c;
		*_efdr+=_Run(l);
	}
	return _efdr;
}

unique_ptr<string> EFDR::code(const string& _data)
{
	string data=_data;
	_Fill_X(data);
	return _Code(data);
}

unique_ptr<string> EFDR::code_dynamic(const string& _data)
{
	string data=_data;
	_Fill_X_Dynamic(data);
	return _Code(data);
}
